PsL Monthly 1993 December/PSL Monthly Shareware CD-ROM (December 1993).iso/prgmming/dos/pascal/tpref.exe/TPR3B.TXT

Text File | 1992-10-19 | 63KB | 1,625 lines

                   Chapter 3
                 - continued -
                 - Part 2 of 3 parts -
                                    of the
                            Turbo Pascal Reference

                           The Turbo Pascal Language


This chapter is part of the Turbo Pascal Reference electronic freeware book (C)
Copyright 1992 by Ed Mitchell.  This freeware book contains supplementary
material to Borland Pascal Developer's Guide, published by Que Corporation,
1992.  However, Que Corporation has no affiliation with nor responsibility for
the content of this free book.  Please see Chapter 1 of the Turbo Pascal
Reference for important information about your right to distribute and use this
material freely.  If you find this material of use, I would appreciate your
purchase of one my books, such as the Borland Pascal Developer's Guide or
Secrets of the Borland C++ Masters, Sams Books, 1992.  Thank you.


Pointers and Complex Data Structures
     Turbo Pascal provides a large variety of built-in data types.  However, to
create specific data structures such as list, queues, stacks, trees and so on,
requires that you create and maintain the appropriate data structures yourself.
Pointers are used extensively to create these types of data structures.
     Figure 3.4 illustrates a list structure containing a list of filenames.
Each filename is stored in a record, together with pointers to the next and
previous items in the list.

***03tpr04.pcx***
Figure 3.4.  Pointers are often used in record structures to create list data
structures, as shown here.  In a list, each element is linked, via a pointer,
to another element in the list.

     Such a list structure is represented as a Pascal record, containing space
for the filename and other information, plus pointer values to the next and
previous list entries.  Listing 3.6 shows a sample data record declared as the
type TListEntry.  A pointer to TListEntry is defined as PListEntry.


Listing 3.6.  A sample data record set up for use in a list data structure.
Note the use of the separate PListEntry, defined as a pointer to TListEntry.

type
     { Data record to create the list structure }
     PListEntry = ^TListEntry;
     TListEntry = record
       DirInfo : SearchRec;
       Next    : PListEntry;
       Previous: PListEntry;
     end; {TListEntry}

A list is constructed out of these records by creating a pointer to the first
item in the list, and storing the first pointer in a variable called ListHead,
and using New ( PListEntry ) to create each entry.   The variable ListTail
points to the last item in the list.

     var
       ListHead : PListEntry;
       ListTail : PListEntry;

     The Next field of the TListEntry record is used to point to the next
succeeding item in the list.  Each time an item is added to the list, the
previous item's Next field is set to point to the new item, and the new item's
Next field, if its the last item in the list, is set to nil to mark the end of
the list.
     The Previous field is used to link the list of items in both directions.
In this way, the items in the list can be accessed in both the forward and the
backwards directions.
     Listing 3.7 presents a complete sample list program that reads the names
of the files from the current subdirectory and places them into a list data
structure.  The program then displays the list in both the forward and backward
directions, using the Next or Previous pointer to reach the next or previous
element in the list structure.

Listing 3.7.  This program uses pointers to create and manipulate a list data
structure.
   1  program DemoList;
   2  {
   3  Demonstrates the use of pointers to create a list structure, demonstrates
how
   4  list traversal is done in both forwards and backwards directions, and
provides
   5  routines to add (or insert) and delete items in the list.
   6
   7  You can modify these routines for use as a general purpose list
manipulation
   8  tool, by changing the ListEntry data structure to hold other types of
data.
   9
  10  This demonstration program uses the Dos library routines FindFirst and
  11  FindNext to read the default file subdirectory.
  12  }
  13  uses  Dos;
  14
  15  type
  16    { Data record to create the list structure }
  17    PListEntry = ^TListEntry;
  18    TListEntry = record
  19      DirInfo : SearchRec;
  20      Next    : PListEntry;
  21      Previous: PListEntry;
  22    end; {TListEntry}
  23
  24  var
  25    ListHead : PListEntry;
  26    ListTail : PListEntry;
  27
  28
  29  function LowerCase (S : String ) : String;
  30  Var
  31    I : Integer;
  32  begin
  33    for I := 1 to length(s)  do
  34      if ((S[I]>='A') and (S[I]<='Z'))  then
  35        S[I] :=  Chr( Ord( S[I] ) + 32 );
  36    LowerCase := S;
  37  end;
  38
  39
  40
  41  procedure InitDirectoryList;
  42  { Initialize the directory list structure.
  43    For convenience, the first entry contains the default volumne name C:\.
  44  }
  45  begin
  46    ListHead := New(PListEntry);
  47    ListHead^.Next := NIL;
  48    ListHead^.Previous := NIL;
  49    ListTail := ListHead;
  50    ListHead^.DirInfo.Name := 'C:\';
  51  end; {InitDirectoryList}
  52
  53
  54
  55  function  AddEntry (     Location : PListEntry;
  56                       Var ListEntry : SearchRec ) : PListEntry;
  57  Var
  58    NewEntry  : PListEntry;
  59    SavedNext : PListEntry;
  60
  61  begin
  62    NewEntry := New ( PListEntry );
  63    NewEntry^.DirInfo := ListEntry;
  64
  65    If  Location = ListTail  Then
  66    {Adding an item on to the tail of the list}
  67    begin
  68      NewEntry^.Next := NIL;
  69      NewEntry^.Previous := ListTail;
  70      ListTail^.Next := NewEntry;
  71      ListTail := NewEntry;
  72    end
  73    else
  74    {inserting an item within the list}
  75    begin
  76      SavedNext := Location^.Next;
  77      Location^.Next := NewEntry;
  78
  79      NewEntry^.Next := SavedNext;
  80      NewEntry^.Previous := Location;
  81
  82      SavedNext^.Previous := NewEntry;
  83
  84    end;{begin}
  85
  86    AddEntry := NewEntry;
  87
  88  end;{AddEntry}
  89
  90
  91
  92  function  RemoveEntry ( Location : PListEntry;
  93                          HowMany  : Integer ) : PListEntry;
  94
  95  { Starting at the point in the list indicated by 'Location', delete
  96    'HomeMany' entries from the list.
  97    Return:  A pointer to the first item after those that were deleted.
  98  }
  99
 100  var
 101    CountOfItems : Integer;
 102
 103    function DeleteEntry ( Location : PListEntry ) : PListEntry;
 104    begin
 105      if  Location <> NIL  then
 106      begin
 107        If  Location^.Previous <> NIL  Then
 108          Location^.Previous^.Next := Location^.Next;
 109        If  Location^.Next <> NIL  Then
 110          Location^.Next^.Previous := Location^.Previous;
 111        DeleteEntry := Location^.Next;
 112        If  Location = ListTail  Then
 113          ListTail := Location^.Previous;
 114        Dispose(Location);
 115      end
 116      else
 117        DeleteEntry := NIL;
 118    end;
 119
 120  begin {RemoveEntry}
 121    For  CountOfItems := 1 to HowMany Do
 122      Location := DeleteEntry ( Location );
 123    RemoveEntry := Location;
 124  end;{RemoveEntry}
 125
 126
 127  function Move_Fwd ( Location : PListEntry;
 128                      HowFar : Integer ) : PListEntry;
 129  {Starting from 'location' move ahead 'HowFar' items in the list
 130   and return the new location
 131  }
 132  Var
 133    I : Integer;
 134  begin
 135    For  I := 1 to HowFar  Do
 136      If  Location^.Next <> NIL  Then
 137        Location := Location^.Next;
 138    Move_Fwd := Location;
 139  end;{Move_Fwd}
 140
 141
 142  function Move_Bwd ( Location : PListEntry;
 143                      HowFar : Integer ) : PListEntry;
 144  {Starting from 'location' move backwards 'HowFar' items in t